package 刷题10月.leecodehot100;

public class demo {
    public static void main(String[] args) {
        int arr[]={1,5,12,8,4,3};
        quickSort(arr,0,arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
    public static void quickSort(int arr[],int left,int rigth){
        if(left>rigth){
            return;
        }
        int temp=arr[left];//轴
        int i=left;
        int j=rigth;
        while (i!=j){//相遇
            while (arr[j]>=temp&&j>i){//先从右边向左走
                j--;
            }
            while(arr[i]<=temp&&j>i){//i向前 遇到大于轴的数，i不动
                i++;
            }
            if(j>i){//交换
                int t=arr[i];
                arr[i]=arr[j];
                arr[j]=t;
            }
        }
        //相遇
        arr[left]=arr[i];
        arr[i]=temp;
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,rigth);
    }
}
